package 链表和树.二叉树;

import java.util.Arrays;

//Java：从前序与中序遍历序列构造二叉树
public class ConstructBinaryTreeFromPreorderAndInorderTraversal{
    public static void main(String[] args) {
        Solution solution = new ConstructBinaryTreeFromPreorderAndInorderTraversal().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
//    public class TreeNode {
//        int val;
//        TreeNode left;
//        TreeNode right;
//        TreeNode() {}
//        TreeNode(int val) { this.val = val; }
//        TreeNode(int val, TreeNode left, TreeNode right) {
//            this.val = val;
//            this.left = left;
//            this.right = right;
//        }
//    }
class Solution {
        //核心解法主要是通过所给的前序和中序反推左右子树的顺序，然后再继续往下面推属于递归问题返回二叉树的首届点
        //Arrays.copyOfRange作用：从一个数组中截取一个子区间，生成一个新的数组。
    //语法：Arrays.copyOfRange(original, from, to)，包括下标 from，不包括下标 to：
        //新数组的长度为 to - from。
        //目标数组元素来自 original[from] 到 original[to - 1]。

//最初调用 buildTree([3,9,20,15,7], [9,3,15,20,7])
//根节点是 3，左子树是 [9]，右子树是 [20,15,7]
//递归构建左子树和右子树
//左子树 buildTree([9], [9])
//根节点是 9，没有左右子树
//返回 TreeNode(9, null, null)
//右子树 buildTree([20,15,7], [15,20,7])
//根节点是 20，左子树是 [15]，右子树是 [7]
//递归构建左子树和右子树
//右子树的左子树 buildTree([15], [15])
//根节点是 15，没有左右子树
//返回 TreeNode(15, null, null)
//右子树的右子树 buildTree([7], [7])
//根节点是 7，没有左右子树
//返回 TreeNode(7, null, null)
//完成右子树的构建
//返回 TreeNode(20, TreeNode(15, null, null), TreeNode(7, null, null))
//最终构建完整的树
//返回 TreeNode(3, TreeNode(9, null, null), TreeNode(20, TreeNode(15, null, null), TreeNode(7, null, null)))
            public TreeNode buildTree(int[] preorder, int[] inorder) {
                int n = preorder.length;
                if (n == 0) { // 空节点也就是前序遍历中根节点都没有了
                    return null;
                }
                //preorder[0] 获得根节点再以此进行左右子树的分割
                int leftSize = indexOf(inorder, preorder[0]);
                int[] pre1 = Arrays.copyOfRange(preorder, 1, 1 + leftSize);
                int[] pre2 = Arrays.copyOfRange(preorder, 1 + leftSize, n);
                int[] in1 = Arrays.copyOfRange(inorder, 0, leftSize);
                int[] in2 = Arrays.copyOfRange(inorder, 1 + leftSize, n);
                TreeNode left = buildTree(pre1, in1);//对左子树继续分左右子树
                TreeNode right = buildTree(pre2, in2);//对右子树继续分左右子树
                return new TreeNode(preorder[0], left, right);
            }

            // 返回 x 在 a 中的下标，保证 x 一定在 a 中
            private int indexOf(int[] a, int x) {
                for (int i = 0; ; i++) {
                    if (a[i] == x) {
                        return i;
                    }
                }
            }


        }


}
//leetcode submit region end(Prohibit modification and deletion)